/*
 * @lc app=leetcode.cn id=2055 lang=cpp
 *
 * [2055] 蜡烛之间的盘子
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <map>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>>& queries) {
        //预处理+前缀和
        int n = s.length();
        //preSum[i]代表位置i前盘子的数量
        vector<int> preSum(n);
        for (int i = 0, sum = 0; i < n; i++) {
            if (s[i] == '*') {
                sum++;
            }
            preSum[i] = sum;
        }
        vector<int> left(n);
        //left(n)代表位置i左边的最近盘子的位置
        for (int i = 0, l = -1; i < n; i++) {
            if (s[i] == '|') {
                l = i;
            }
            left[i] = l;
        }
        vector<int> right(n);
        //right(n)代表位置i右边的最近盘子的位置
        for (int i = n - 1, r = -1; i >= 0; i--) {
            if (s[i] == '|') {
                r = i;
            }
            right[i] = r;
        }
        vector<int> ans;
        
        for (auto& query : queries) {
            int x = right[query[0]], y = left[query[1]];
            ans.push_back(x == -1 || y == -1 || x >= y ? 0 : preSum[y] - preSum[x]);
        }
        return ans;
    }
};
// @lc code=end


//记录蜡烛左边盘子数量的方法超时
// int n = queries.size();
//         map<int,int> record;
//         vector<int> ans;
//         int num = 0;
//         for(int i = 0;i < s.length();i++) {
//             if(s[i] == '*') {
//                 if(!record.empty()) {
//                     num++;
//                 }
//             }else {
//                 record.insert(make_pair(i,num));
//             }
//         }
//         for(auto q: queries) {
//             int left = 0,right = ;
//             for(int i = q[0];i <= q[1];i++) {
//                 if(s[i] == '|') {
//                     left = record.at(i);
//                     break;
//                 }
//             }
//             for(int i = q[1];i >= q[0];i--) {
//                 if(s[i] == '|') {
//                     right = record.at(i);
//                     break;
//                 }
//             }
//             ans.push_back(right - left);
//         }
//         return ans;

